Scheduling elevator cars is a practical optimization problem for banks of elevators in buildings. The object is to assign arriving passengers to cars so as to optimize one or more performance criteria such as waiting time, total transfer time, percentage of people waiting longer than a specific threshold, or fairness of service.
The scheduling of elevator cars is a hard combinatorial optimization problem due to the very large number of possible solutions (the solution space), uncertainty arising from unknown destination floors of newly arriving passengers, and from unknown arrival times of future passengers.
The most commonly accepted optimization criterion is the average waiting time (AWT) of arriving passengers, G. C. Barney, “Elevator Traffic Handbook,” Spon Press, London, 2003; G. R. Strakosch, “Vertical transportation: elevators and escalators,” John Wiley & Sons, Inc., New York, N.Y., 1998; and G. Bao, C. G. Cassandras, T. E. Djaferis, A. D. Gandhi, and D. P. Looze, “Elevator dispatchers for downpeak traffic,” Technical report, University of Massachusetts, Department of Electrical and Determiner Engineering, Amherst, Mass., 1994.
Another important consideration is the social protocol under which the scheduler is operating. In some countries, e.g., Japan, each assignment is made at the time of the hall call of the arriving passenger, and the assignment is not changed until the passenger is served. This is called an immediate policy. In other countries, e.g., the U.S., the system can reassign hall calls to different cars if this improves the schedule. This is called a reassignment policy. While the reassignment policy increases the computational complexity of scheduling, the additional degrees of freedom can be exploited to achieve major improvements of the AWT.
In practice, it is assumed that passenger dissatisfaction grows supra-linearly as a function of the AWT. When minimizing objective functions, one penalizes long waits much stronger than short waits, which helps to reduce extensive long waits, see M. Brand and D. Nikovski, “Risk-averse group elevator scheduling,” Technical report, Mitsubishi Electric Research Laboratories, Cambridge, Mass., 2004; and U.S. patent application Ser. No. 10/161,304, “Method and System for Dynamic Programming of Elevators for Optimal Group Elevator Control,” filed by Brand et al. on Jun. 3, 2002, both incorporated herein by reference.
Another method determines the AWT of existing passengers and future passengers, Nikovski et al., “Decision-theoretic group elevator scheduling,” 13th International Conference on Automated Planning and Scheduling, June 2003; and U.S. patent application Ser. No. 10/602,849, “Method and System for Scheduling Cars in Elevator Systems Considering Existing and Future Passengers,” filed by Nikovski et al. on Jun. 24, 2003, both incorporated herein by reference. That method is referred to as the “Empty the System Algorithm by Dynamic Programming” (ESA-DP) method.
The EAS-DP method determines a substantially exact estimation of waiting times. The method takes into account the uncertainty arising from unknown destination floors of passengers not yet been served, or passengers that have not yet indicated their destination floor. That method represents the system by a discrete-state Markov chain and makes use of dynamic programming to determine the AWT averaged over all possible future states of the system. Despite of the large state space, the performance of the method is linear in the number of floors of the building and number of shafts, and quadratic in the number of arriving passengers.
The run time of ESA-DP method is completely within the possibilities of modern micro-controllers and the quality of its solutions lead to major improvements when compared with other scheduling methods. However, that method does not exploit the additional potential of elevator systems operating according to the reassignment policy.